package part_2;

import genetic_algorithm.Chromosome;
import genetic_algorithm.GA;

import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Random;

/**
 * this class implements the GA algorithm for solving the tsp problem
 */
public class GA_TSP_alg implements GA
{

	// the population size
	int POPULATION_SIZE=100;
	// the percentage for performing a mutation an a child chromosome
	int MUTATION_RATE=500;
	// the number of generations
	int NUM_OF_GENERATIONS=6000;
	// the percentage of performing crossover between two parents 
	int CROSSOVER_RATE=95;
	// the number of cities for the tsp problem
	int NUM_CITIES;
	// an array for holding the positions of the cities in the tsp problem
	ArrayList<int[]> cities_locs;

	/**
	 * this function run the GA algorithm for the tsp problem
	 * @param cities_locs - an array for holding the positions of the cities in the tsp problem
	 * @param right_solution - the best route for this specific tsp problem
	 * @throws IOException
	 */
	public void run_alg(ArrayList<int[]> cities_locs, ArrayList<Integer> right_solution) throws IOException
	{
		// Initialize variables
		this.cities_locs = cities_locs;
		NUM_CITIES=cities_locs.size();
		TspChromosome.cities_locs=cities_locs;
		double avg;

		// get the fitness of the best solution
		double right_solution_fitness=(new TspChromosome(right_solution)).evaluateFitness();

		// objects for writing the needed data for the learning graphs
		FileWriter fw=new FileWriter("tsp_graph4.csv");
		fw.write("num_generation,best_fitness,avg_fitness");
		fw.write('\n');

		Random r=new Random();

		// initialize the population
		ArrayList<Chromosome> population=initiate_population(POPULATION_SIZE);


		int count=0;
		ArrayList<Chromosome> selected;
		ArrayList<Chromosome> children;

		// for each generation
		while(count<NUM_OF_GENERATIONS)
		{
			Chromosome best=getMaxAndRemoveWorst(population);
			// the case that the GA found the optimal solution for this tsp problem
			if(best.evaluateFitness()== right_solution_fitness)
			{
				break;
			}

			fw.write(count+","+best.evaluateFitness());


			population.remove(best);
			Chromosome second_best=getMaxAndRemoveWorst(population);
			population.add(best);

			// calculating the average fitness
			avg=calcAvgFitness(population);

			fw.write(","+avg);
			fw.write('\n');

			// selecting the parents for crossover
			selected=selection(population,avg);
			population.clear();
			
			// initiating the not picked array to all the cities
			ArrayList<Integer> indexes_not_chosen_yet=new ArrayList<Integer>();
			for(int i=0;i<POPULATION_SIZE-2;i++)
				indexes_not_chosen_yet.add(i);
			
			int index1,index2;
			// for every random two parents from the selection array
			for(int i=0;i<POPULATION_SIZE-2;i+=2)
			{
				index1=r.nextInt(indexes_not_chosen_yet.size());
				int first_index=indexes_not_chosen_yet.get(index1);
				indexes_not_chosen_yet.remove(index1);
				index2=r.nextInt(indexes_not_chosen_yet.size());
				int second_index=indexes_not_chosen_yet.get(index2);
				indexes_not_chosen_yet.remove(index2);

				// performing crossover between two parents
				children=crossover(selected.get(second_index),selected.get(first_index));
				// adding thos new children to the next population
				population.addAll(children);
			}

			// replacting the two best chromosome from this generation to the next one
			population.add(best);
			population.add(second_best);
			
			count++;
		}

		// getting the best route the GA has found
		Chromosome final_solution=getBestSolution(population);
		
		System.out.println(final_solution.getData());
		System.out.println("our GA price "+ final_solution.evaluateFitness());
		System.out.println("best price "+ right_solution_fitness);
		System.out.println("difference "+( right_solution_fitness- final_solution.evaluateFitness()));

		fw.close();
	}

	/*
	 * this function return the chromosome with the best fitness in the population
	 * and removes the one the the worst 
	 * @param population - the current population
	 * @return - the best chromosome in the population
	 */
	private Chromosome getMaxAndRemoveWorst(ArrayList<Chromosome> population)
	{
		int max_fitness=-2000000;
		int max_index=-1;

		int min_fitness=2;
		int min_index=-1;
		
		// for every chromosome in the population 
		for(int i=0;i<population.size();i++)
		{
			// the case that this chromosome's fitness is bigger then the current maximal
			if(population.get(i).evaluateFitness()>max_fitness)
			{
				// update the maxium fitness
				max_fitness=(int) population.get(i).evaluateFitness();
				max_index=i;
			}
			
			// the case that this chromosome's fitness is lower then the current minimal
			if(population.get(i).evaluateFitness()<min_fitness)
			{
				// update the minimum fitness
				min_fitness=(int) population.get(i).evaluateFitness();
				min_index=i;
			}
		}


		Chromosome best=population.get(max_index);
		// remove the worst
		population.remove(min_index);
		return best;
	}

	/*
	 * this function return the chromosome with the best fitness in the population
	 * @param population - the current population
	 * @return - the best chromosome in the population
	 */
	private Chromosome getBestSolution(ArrayList<Chromosome> population)
	{
		int max_fitness=-2000000;
		int max_index=-1;

		// for every chromosome in the population 
		for(int i=0;i<population.size();i++)
		{
			// the case that this chromosome's fitness is bigger then the current maximal
			if(population.get(i).evaluateFitness()>max_fitness)
			{
				// update the maxium fitness
				max_fitness=(int) population.get(i).evaluateFitness();
				max_index=i;
			}

		}

		Chromosome best=population.get(max_index);
		return best;
	}
	
	/**
	 * this function initiate the first population of chromosomes with random values
	 * @param size - the population size
	 * @return - the first population
	 */
	@Override
	public ArrayList<Chromosome> initiate_population(int size) 
	{
		// Initialize variables
		Random r = new Random();
		int city;
		ArrayList<Chromosome> population=new ArrayList<Chromosome>(size);
		int index;
		int[] cities_indexes=new int[NUM_CITIES];		
		ArrayList<Integer> route;
		
		// initialize every chromosome in the first population
		for(int i=0;i<size;i++)
		{
			route=new ArrayList<Integer>();

			// get all the cities indexes
			for(int k=0;k<NUM_CITIES;k++)
			{
				cities_indexes[k]=k;
			}

			// for every part of the route
			for(int j=0;j<NUM_CITIES;j++)
			{
				// choose a random city
				index=r.nextInt(NUM_CITIES-j);
				// add it to the route
				route.add(cities_indexes[index]);
				// replacing the chosen city with city in place "NUM_CITIES-j-1"
				city=cities_indexes[NUM_CITIES-j-1];
				cities_indexes[NUM_CITIES-j-1]=index;
				cities_indexes[index]=city;
			}

			// solving the indexes problem
			for(int j=0;j<NUM_CITIES;j++)
			{
				route.set(j, route.get(j)+1);
			}


			population.add(new TspChromosome(route));
		}

		return population;
	}



	/*
	 * this function calculate the exp value for the i-th chromosome in the population
	 * @param i - the index for the chromosome
	 * @param population - the current population
	 * @param avg - this population fitness's average
	 * @return - the exp value
	 */
	private double ExpVal(int i,ArrayList<Chromosome> population,double avg)
	{
		return (population.get(i).evaluateFitness())/avg;
	}



	/*
	 * this function calculates the average fitness of the given population
	 * @param population - the current population
	 * @return - the average fitness of this population
	 */
	private double calcAvgFitness(ArrayList<Chromosome> population){

		double sum=0;

		// for every chromosome in the population
		for(Chromosome chrm:population)
		{
			// add this chromosome fitness
			sum+=chrm.evaluateFitness();
		}

		// return the average fitness
		return ((double)sum)/population.size();
	}


	/**
	 * this function selects the parents for the crossover operation
	 * @param population - the current population
	 * @param avg - the average fitness of the population
	 * @return - the selected parents for the crossover
	 */
	@Override
	public ArrayList<Chromosome> selection(ArrayList<Chromosome> population,double avg)
	{
		int N = population.size();
		int T=N;

		Random r=new Random();
		// get a random number
		double num=r.nextInt(T);
		double sum = 0.0;
		int j;

		ArrayList<Chromosome> selected=new ArrayList<Chromosome>();

		// choose N parents
		for(int i=0;i<N;i++)
		{
			// for each chromosome in the population
			for(j=0;j<N;j++)
			{
				// add the exp value to the sum
				sum+=ExpVal(j,population,avg);
				// the case that this "j" chromosome was selected
				if(sum>num)
				{	
					selected.add(population.get(j));
					// change in fixed distance
					num = (num+((double)T/N)) % T;
					sum = 0.0;
					break;
				}
			} 
		}
		
		return selected;
	}


	/**
	 * this function returns two children from the reproduction of parent1 and parent2
	 * @param parent1 - the first parent chromosome
	 * @param parent2 - the second parent chromosome
	 * @return - the two children of this parents
	 */
	@Override
	public ArrayList<Chromosome> crossover(Chromosome parent1,
			Chromosome parent2) {
		  //first try-simplest correction
		 //_____________________________________
		 

/*

		Random r=new Random();

		ArrayList<Chromosome> children=new ArrayList<Chromosome>();

		ArrayList<Integer> child1=new ArrayList<Integer>();
		ArrayList<Integer> child2=new ArrayList<Integer>();
		int num;

		num=r.nextInt(100);

		if(num>=CROSSOVER_RATE)
		{
			children.add(parent1);
			children.add(parent2);
			return children;
		}

		for(int i=0;i<NUM_CITIES;i++)
		{
			num=r.nextInt(2);
			if(num==0)
			{
				child1.add(parent1.getData().get(i));
				child2.add(parent2.getData().get(i));
			}
			else
			{
				child1.add(parent2.getData().get(i));
				child2.add(parent1.getData().get(i));
			}

		}

		ArrayList<Integer> not_appeared_yet1=new ArrayList<Integer>();
		ArrayList<Integer> not_appeared_yet2=new ArrayList<Integer>();
		for(int i=0;i<NUM_CITIES;i++)
		{
			not_appeared_yet1.add(i+1);
			not_appeared_yet2.add(i+1);
		}

		for(int i=0;i<child1.size();i++)
		{
			if(!not_appeared_yet1.contains(child1.get(i)))
				child1.set(i, -1);
			else
				not_appeared_yet1.remove(new Integer(child1.get(i)));

			if(!not_appeared_yet2.contains(child2.get(i)))
				child2.set(i, -1);
			else
				not_appeared_yet2.remove(new Integer(child2.get(i)));

		}

		for(int i=0;i<child1.size();i++)
		{
			if(child1.get(i)==-1)
			{
				num=r.nextInt(not_appeared_yet1.size());
				child1.set(i,not_appeared_yet1.get(num));
				not_appeared_yet1.remove(num);
			}
			if(child2.get(i)==-1)
			{
				num=r.nextInt(not_appeared_yet2.size());
				child2.set(i,not_appeared_yet2.get(num));
				not_appeared_yet2.remove(num);
			}
		}

		children.add(mutation(new TspChromosome(child1)));
		children.add(mutation(new TspChromosome(child2)));


		//System.out.println("parent1:"+parent1.getData());
		//System.out.println("parent2:"+parent2.getData());
		//System.out.println("child1:"+child1);
		//System.out.println("child2"+child2);
		//System.out.println("_________________________________________________-");

		return children;
*/
		 


		  //second try-random start cross....
		 //_____________________________________
		  
	/*	Random r=new Random();

		ArrayList<Chromosome> children=new ArrayList<Chromosome>();

		ArrayList<Integer> child1=new ArrayList<Integer>();
		ArrayList<Integer> child2=new ArrayList<Integer>();
		int num;

		num=r.nextInt(100);

		if(num>=CROSSOVER_RATE)
		{
			children.add(parent1);
			children.add(parent2);
			return children;
		}

		int parent1_index=r.nextInt(NUM_CITIES);
		//int parent1_index=4;
		//System.out.println("the city:"+parent1.getData().get(parent1_index));
		int parent2_index = 0;
		for(int i=0;i<NUM_CITIES;i++)
		{
			if(parent2.getData().get(i)==parent1.getData().get(parent1_index))
			{
				parent2_index=i;
				break;
			}
		}

		//System.out.println("parent1_index:"+parent1_index);
		//System.out.println("parent2_index:"+parent2_index);
		for(int i=0;i<NUM_CITIES;i++)
		{
			child1.add(-1);
			child2.add(-1);
		}

		int child1_index=Math.abs(parent2_index-parent1_index);
		int child2_index=child1_index;
		child1.set(child1_index,parent1.getData().get(parent1_index));
		child2.set(child2_index,parent1.getData().get(parent1_index));

		ArrayList<Integer> already_appeared=new ArrayList<Integer>();
		already_appeared.add(parent1.getData().get(parent1_index));
		boolean parent1_contradicted=false,parent2_contradicted=false;
		while(!parent1_contradicted || !parent2_contradicted)
		{
			parent1_index--;
			child1_index--;
			child2_index++;
			if(child1_index<0 || child2_index>=NUM_CITIES || parent1_index<0)
				break;
			int parent1_elem=parent1.getData().get(parent1_index);
			if(!parent1_contradicted && !already_appeared.contains(parent1_elem))
			{
				//System.out.println("child1_index:"+child1_index);
				//System.out.println("child2_index:"+child2_index);
				child1.set(child1_index, parent1_elem);
				child2.set(child2_index, parent1_elem);
				already_appeared.add(parent1_elem);
			}
			else
			{
				parent1_contradicted=true;
				if(parent2_contradicted)
					break;


				parent2_index++;
				if(parent2_index>=parent2.getData().size())
					break;
				int parent2_elem=parent2.getData().get(parent2_index);
				if(!already_appeared.contains(parent2_elem))
				{
					child1.set(child1_index, parent2_elem);
					child2.set(child2_index, parent2_elem);
					already_appeared.add(parent2_elem);
				}
				else
				{
					parent2_contradicted=true;
					break;
				}

			}

			parent2_index++;
			//child1_index--;
			//child2_index++;

			if(child1_index<0 || child2_index>=NUM_CITIES)
				break;


			if(parent2_index>=parent2.getData().size())
				break;
			int parent2_elem=parent2.getData().get(parent2_index);

			if(!parent2_contradicted && !already_appeared.contains(parent2_elem))
			{
				child1.set(child2_index, parent2_elem);
				child2.set(child1_index, parent2_elem);

				already_appeared.add(parent2_elem);
			}
			else
			{
				parent2_contradicted=true;
				if(parent1_contradicted)
					break;

				parent1_index--;
				if(parent1_index<0)
					break;
				int parent1_elem_new=parent1.getData().get(parent1_index);
				if(!already_appeared.contains(parent1_elem_new))
				{
					child1.set(child2_index, parent1_elem_new);
					child2.set(child1_index, parent1_elem_new);
					already_appeared.add(parent1_elem_new);
				}
				else
				{
					parent1_contradicted=true;
					break;
				}
			}


		}

		ArrayList<Integer> not_appear_yet1=new ArrayList<Integer>();
		ArrayList<Integer> not_appear_yet2=new ArrayList<Integer>();
		for(int i=0;i<NUM_CITIES;i++)
		{
			if(!already_appeared.contains(i+1))
			{
				not_appear_yet1.add(i+1);
				not_appear_yet2.add(i+1);
			}
		}
		for(int i=0;i<NUM_CITIES;i++)
		{
			if(child1.get(i)==-1)
			{
				num=r.nextInt(not_appear_yet1.size());
				child1.set(i, not_appear_yet1.get(num));
				not_appear_yet1.remove(num);
			}
			if(child2.get(i)==-1)
			{
				num=r.nextInt(not_appear_yet2.size());
				child2.set(i, not_appear_yet2.get(num));
				not_appear_yet2.remove(num);
			}
		}

			children.add(mutation(new TspChromosome(child1)));
			children.add(mutation(new TspChromosome(child2)));
			return children;
		 

		*/

		Random r=new Random();

		ArrayList<Chromosome> children=new ArrayList<Chromosome>();

		ArrayList<Integer> child1=new ArrayList<Integer>();
		ArrayList<Integer> child2=new ArrayList<Integer>();
		int num;

		// get a random number (between 0 and 100)
		num=r.nextInt(100);

		// the case that this time the two parents will continue to the next generation with no crossover
		if(num>=CROSSOVER_RATE)
		{
			children.add(parent1);
			children.add(parent2);
			return children;
		}

		num = r.nextInt(2);

		Integer elem1 = parent1.getData().get(0);
		Integer elem2 = parent2.getData().get(0);
		Integer option1, option2;
		// the case that the first child will start like parent one and the second child will start like parent two
		if(num == 0)
		{
			child1.add(elem1);
			child2.add(elem2);
		}
		// the case that the first child will start like parent two and the second child will start like parent one
		else
		{
			child1.add(elem2);
			child2.add(elem1);
		}

		// for every city in the parents route
		for (int j = 1; j < NUM_CITIES; j++) 
		{
			// get the last updated city in the cildren
			elem1 = child1.get(j-1);
			elem2 = child2.get(j-1);
			// get the next optional cities in the parents
			option1 = parent1.getData().get(j);
			option2 = parent2.getData().get(j);

			// the case that child 1 should greedly choose to go to parent one optional city
			if(calcDistance(elem1, option1) < calcDistance(elem1, option2))
			{
				child1.add(option1);
			}
			// the case that child 1 should greedly choose to go to parent two optional city
			else
			{
				child1.add(option2);
			}

			// the case that child 2 should greedly choose to go to parent one optional city
			if(calcDistance(elem2, option1) < calcDistance(elem2, option2))
			{
				child2.add(option1);
			}
			// the case that child 2 should greedly choose to go to parent two optional city
			else
			{
				child2.add(option2);
			}
		}
		
		ArrayList<Integer> not_appeared_yet1=new ArrayList<Integer>();
		ArrayList<Integer> not_appeared_yet2=new ArrayList<Integer>();
		// adding all of the cities to the no appeared arrays
		for(int i=0;i<NUM_CITIES;i++)
		{
			not_appeared_yet1.add(i+1);
			not_appeared_yet2.add(i+1);
		}

		// for each city in the children's route
		for(int i=0;i<child1.size();i++)
		{
			// the case that this city in child1 has not already appeared 
			if(!not_appeared_yet1.contains(child1.get(i)))
				child1.set(i, -1);
			// the case that this city in child1 has already appeared
			else
				not_appeared_yet1.remove(new Integer(child1.get(i)));

			// the case that this city in child2 has not already appeared
			if(!not_appeared_yet2.contains(child2.get(i)))
				child2.set(i, -1);
			// the case that this city in child2 has already appeared
			else
				not_appeared_yet2.remove(new Integer(child2.get(i)));
		}

		// for each city in the children's route
		for(int i=0;i<child1.size();i++)
		{
			// the case that this index needs a new city
			if(child1.get(i)==-1)
			{
				// getting a random new legal city
				num=r.nextInt(not_appeared_yet1.size());
				// and adding it to the child's route
				child1.set(i,not_appeared_yet1.get(num));
				not_appeared_yet1.remove(num);
			}
			
			// the case that this index needs a new city
			if(child2.get(i)==-1)
			{
				// getting a random new legal city
				num=r.nextInt(not_appeared_yet2.size());
				// and adding it to the child's route
				child2.set(i,not_appeared_yet2.get(num));
				not_appeared_yet2.remove(num);
			}
		}

		// add the children to the result array (with possiable mutation)
		children.add(mutation(new TspChromosome(child1)));
		children.add(mutation(new TspChromosome(child2)));

		return children;
	}

	/*
	 * this function calculate the distance between the elem and the option city 
	 * @param elem - the first city
	 * @param option - the second city
	 * @return - the distance between them
	 */
	private double calcDistance(Integer elem, Integer option) 
	{
		double dist = 0.0;
		int[] a;
		int[] b;

		a=cities_locs.get(elem.intValue() -1);
		b=cities_locs.get(option.intValue() -1);
		
		// calculate the distance between those two cities
		dist=Math.sqrt(Math.pow(a[0]-b[0],2)+Math.pow(a[1]-b[1],2));

		return dist;
	}

	/**
	 * this function randomly changes chrm at certain probability
	 * @param chrm - the chromosome to change (maybe)
	 * @return - the chromosme after the change
	 */
	@Override
	public Chromosome mutation(Chromosome chrm)
	{
		Random r=new Random();

		int index1,index2,num;
		num=r.nextInt(MUTATION_RATE);
		// the case that this chromosome will have a mutaion on him
		if(num==0)
		{
			// getting two indexes
			index1=r.nextInt(NUM_CITIES);
			index2=r.nextInt(NUM_CITIES);

			int max, min;
			
			// the case that index1 is bigger than index2
			if(index1 > index2)
			{
				max = index1;
				min = index2;
			}
			// the case that index2 is bigger or equal to index1
			else
			{
				max = index2;
				min = index1;
			}
			
			ArrayList<Integer> old_route=chrm.getData();
			ArrayList<Integer> route = new ArrayList<Integer>();

			// copy the same route until the first index
			for (int i = 0; i < min ; i++) 
			{
				route.add(old_route.get(i));
			}

			// copy the same route in reverse until the second index
			for (int i = max; i >= min ; i--) 
			{
				route.add(old_route.get(i));
			}

			// copy the same route until the end of the route
			for (int i = max; i < NUM_CITIES ; i++) 
			{
				route.add(old_route.get(i));
			}

			return new TspChromosome(route);
		}
		// the case that this chromosome will not have a mutaion on him
		else
			return chrm;
	}
}
